
// shift (move) a child array to right by 1 position
void ShiftRight(int a[], int start, int count)
{
	for (int i=start+count; i>start; i--)
		a[i] = a[i-1];
}

// merge 2 child arrays to unique one
// parameters:
//		start: start position of merging array
//		lCount: number of element in 'left' array
//		rCount: number of element in 'right' array
void Merge(int a[], int start, int lCount, int rCount)
{
	// algorithm: the array 'a' is splited to 3 parts
	//		- first part (at beginning) is sorted array
	//		- second part (left part) is a child array to be merged
	//		- third part (right part) is a child array to be merged
	//
	// i: start position of left array
	// j: start position of right array
	// i: the position to be added to first part
	int i=start, j=start+lCount;

	while (i < j && j < start + lCount + rCount)
	{
		// we are choosing either a[i] or a[j] to add to the first part
		if (a[i] < a[j])	// choose a[i]
		{
			i++; // first element is added to first part, move to next element
		}
		else				// choose a[j]
		{
			// temporary store a[j]
			int temp = a[j];
			// shift left part to right by 1
			ShiftRight(a, i, j - i);
			// put temporary value to position i
			a[i] = temp;
			// left part has been shifted right, so i is also increased
			i++;
			// first element of right part is added to first part, move to next element
			j++;
		}
	}
}

void MergeSort(int a[], int left, int right)
{
	// recursive exiting condition
	if (right <= left)
		return;

	// split 'a' to 2 parts
	int center = (left + right) / 2;
	// merge sort the left part
	MergeSort(a, left, center);
	// merge sort the right part
	MergeSort(a, center + 1, right);

	// merge 2 sorted part to unique one
	Merge(a, left, center - left + 1, right - center);
}

int main_merge_sort()
{
	const int n = 11;
	int a[n] = {12, 2, 4, 5, 3, 8, 6, 1, 8, 8, 8};
	MergeSort(a, 0, n-1);

	return 0;
}
